package NewCoder;

import java.util.HashMap;
import java.util.Map;

public class BM40 {
    Map<Integer,Integer> map=new HashMap<>();
    int[] pre;
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        this.pre=pre;
        int n=vin.length;
        for(int i=0;i<n;i++){
            map.put(vin[i],i);
        }
        return build(0,0,n-1);
    }

    /**
     * 根据先序遍历的节点在中序遍历中的位置 得到左子树和右子树 从而构建一棵二叉树
     * @param root 前序遍历的索引
     * @param left 子树在中序遍历中的左边界
     * @param right 子树在中序遍历中的右边界
     * @return
     */
    private TreeNode build(int root,int left,int right){
        if(left>right) return null;
        TreeNode node=new TreeNode(pre[root]);
        int i=map.get(pre[root]);
        node.left=build(root+1,left,i-1);
        node.right=build(root+i-left+1,i+1,right);
        return node;
    }
}
